package unionFindSet;
import java.util.Arrays;

/**
 * 模拟实现: 并查集
 */
public class UnionFindSet {
    int n ;
    int[] elem = null;
    public UnionFindSet(int n) {
        this.n = n;
        elem = new int[n + 1];
        // 刚开始每个人都是 根节点
        Arrays.fill(elem, -1);
    }

    // 返回当前标号的 队长
    public int getRoot(int x) {
        if (x < 0 || x > this.n)    return -1;
        while (elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }

    // 合并
    public void unit(int x, int y) {
        if (x == y) return ; // 同一个目标
        // 如果已经在一个集合里, 就无法合并
        int idx1 = getRoot(x), idx2 = getRoot(y);
        if (idx1 == idx2)   return ;

        elem[idx1] += elem[idx2];
        elem[idx2] = idx1;
    }

    public boolean isConnected(int x, int y) {
        return getRoot(x) == getRoot(y);
    }
}